package string;

/**
 * 给你一个字符串 word 和一个整数 numFriends。
 * Alice 正在为她的 numFriends 位朋友组织一个游戏。游戏分为多个回合，在每一回合中：
 * word 被分割成 numFriends 个 非空 字符串，且该分割方式与之前的任意回合所采用的都 不完全相同 。
 * 所有分割出的字符串都会被放入一个盒子中。
 * 在所有回合结束后，找出盒子中 字典序最大的 字符串。
 * <p>
 * 示例 1：
 * 输入: word = "dbca", numFriends = 2
 * 输出: "dbc"
 * 解释:
 * 所有可能的分割方式为：
 * "d" 和 "bca"。
 * "db" 和 "ca"。
 * "dbc" 和 "a"。
 * <p>
 * 示例 2：
 * 输入: word = "gggg", numFriends = 4
 * 输出: "g"
 * 解释:
 * 唯一可能的分割方式为："g", "g", "g", 和 "g"。
 *
 * @author Jisheng Huang
 * @version 20250604
 */
public class LastStrFromBoxI_3403 {
    public static String lastSubstring(String s) {
        int i = 0;
        int j = 1;
        int n = s.length();

        while (j < n) {
            int k = 0;

            while (j + k < n && s.charAt(i + k) == s.charAt(j + k)) {
                ++k;
            }

            if (j + k < n && s.charAt(i + k) < s.charAt(j + k)) {
                int t = i;
                i = j;
                j = Math.max(j + 1, t + k + 1);
            } else {
                j = j + k + 1;
            }
        }

        return s.substring(i);
    }

    public static String answerString(String word, int numFriends) {
        if (numFriends == 1) {
            return word;
        }

        String last = lastSubstring(word);
        int n = word.length();
        int m = last.length();

        return last.substring(0, Math.min(m, n - numFriends + 1));
    }

    public static void main(String[] args) {
        String word = "dbca";
        int numFriends = 2;

        System.out.println(answerString(word, numFriends));

        word = "gggg";
        numFriends = 4;

        System.out.println(answerString(word, numFriends));
    }
}
